home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 October / EnigmA AMIGA RUN 01 (1995)(G.R. Edizioni)(IT)[!][issue 1995-10][Aminet 7].iso / Aminet / dev / gcc / ixemul_src.lha / ixemul-41.0 / network / bigkey.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  17KB  |  673 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bigkey.c    5.5 (Berkeley) 3/12/91";
  39. #endif /* LIBC_SCCS and not lint */
  40. #undef DEBUG
  41. /******************************************************************************
  42.  
  43. PACKAGE: hash
  44.  
  45. DESCRIPTION: 
  46.     Big key/data handling for the hashing package.
  47.  
  48. ROUTINES: 
  49.     External
  50.     __big_keydata
  51.     __big_split
  52.     __big_insert
  53.     __big_return
  54.     __big_delete
  55.     __find_last_page
  56.     Internal
  57.     collect_key
  58.     collect_data
  59. ******************************************************************************/
  60. /* Includes */
  61. #include <sys/param.h>
  62. #include <assert.h>
  63. #include <errno.h>
  64. #include <db.h>
  65. #include <stdio.h>
  66. #include <stdlib.h>
  67. #include <string.h>
  68. #include "hash.h"
  69. #include "page.h"
  70.  
  71. /* Externals */
  72. /* buf.c */
  73. extern BUFHEAD *__get_buf();
  74.  
  75. /* dynahash.c */
  76. extern    u_int call_hash();
  77.  
  78. /* page.c */
  79. extern BUFHEAD *__add_ovflpage();
  80.  
  81. /* My externals */
  82. extern int __big_keydata();
  83. extern int __big_split();
  84. extern int __big_insert();
  85. extern int __big_return();
  86. extern int __big_delete();
  87. extern u_short __find_last_page();
  88. extern int __find_bigpair();
  89.  
  90. /* My internals */
  91. static int collect_key();
  92. static int collect_data();
  93.  
  94. #ifdef HASH_STATISTICS
  95. extern long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
  96. #endif
  97. /*
  98. Big_insert
  99.  
  100. You need to do an insert and the key/data pair is too big
  101. 0 ==> OK
  102. -1 ==> ERROR
  103. */
  104. extern int
  105. __big_insert ( bufp, key, val )
  106. BUFHEAD *bufp;
  107. DBT    *key, *val;
  108. {
  109.     char    *cp = bufp->page;    /* Character pointer of p */
  110.     register u_short    *p = (u_short *)cp;
  111.     char    *key_data, *val_data;
  112.     int        key_size, val_size;
  113.     int        n;
  114.     u_short    space, move_bytes, off;
  115.  
  116.     key_data = (char *)key->data;
  117.     key_size = key->size;
  118.     val_data = (char *)val->data;
  119.     val_size = val->size;
  120.  
  121.     /* First move the Key */
  122.     for ( space = FREESPACE(p) - BIGOVERHEAD; 
  123.       key_size; 
  124.       space = FREESPACE(p) - BIGOVERHEAD ) {
  125.     move_bytes = MIN(space, key_size);
  126.     off = OFFSET(p) - move_bytes;
  127.     bcopy (key_data, cp+off, move_bytes );
  128.     key_size -= move_bytes;
  129.     key_data += move_bytes;
  130.     n = p[0];
  131.     p[++n] = off;
  132.     p[0] = ++n;
  133.     FREESPACE(p) = off - PAGE_META(n);
  134.     OFFSET(p) = off;
  135.     p[n] = PARTIAL_KEY;
  136.     bufp = __add_ovflpage(bufp);
  137.     if ( !bufp ) {
  138.         return(-1);
  139.     }
  140.     n = p[0];
  141.     if ( !key_size ) {
  142.         if ( FREESPACE(p) ) {
  143.         move_bytes = MIN (FREESPACE(p), val_size);
  144.         off = OFFSET(p) - move_bytes;
  145.         p[n] = off;
  146.         bcopy ( val_data, cp + off, move_bytes );
  147.         val_data += move_bytes;
  148.         val_size -= move_bytes;
  149.         p[n-2] = FULL_KEY_DATA;
  150.         FREESPACE(p) = FREESPACE(p) - move_bytes;
  151.         OFFSET(p) = off;
  152.         }
  153.         else p[n-2] = FULL_KEY;
  154.     }
  155.     p = (u_short *)bufp->page;
  156.     cp = bufp->page;
  157.     bufp->flags |= BUF_MOD;
  158.     }
  159.  
  160.     /* Now move the data */
  161.     for ( space = FREESPACE(p) - BIGOVERHEAD; 
  162.       val_size; 
  163.       space = FREESPACE(p) - BIGOVERHEAD ) {
  164.     move_bytes = MIN(space, val_size);
  165.     /*
  166.         Here's the hack to make sure that if the data ends
  167.         on the same page as the key ends, FREESPACE is
  168.         at least one
  169.     */
  170.     if ( space == val_size && val_size == val->size ) {
  171.         move_bytes--;
  172.     }
  173.     off = OFFSET(p) - move_bytes;
  174.     bcopy (val_data, cp+off, move_bytes );
  175.     val_size -= move_bytes;
  176.     val_data += move_bytes;
  177.     n = p[0];
  178.     p[++n] = off;
  179.     p[0] = ++n;
  180.     FREESPACE(p) = off - PAGE_META(n);
  181.     OFFSET(p) = off;
  182.     if ( val_size ) {
  183.         p[n] = FULL_KEY;
  184.         bufp = __add_ovflpage (bufp);
  185.         if ( !bufp ) {
  186.         return(-1);
  187.         }
  188.         cp = bufp->page;
  189.         p = (u_short *)cp;
  190.     } else {
  191.         p[n] = FULL_KEY_DATA;
  192.     }
  193.     bufp->flags |= BUF_MOD;
  194.     }
  195.     return(0);
  196. }
  197.  
  198. /*
  199.     Called when bufp's page  contains a partial key (index should be 1)
  200.  
  201.     All pages in the big key/data pair except bufp are freed.  We cannot
  202.     free bufp because the page pointing to it is lost and we can't
  203.     get rid of its pointer.
  204.  
  205.     Returns 0 => OK
  206.         -1 => ERROR
  207. */
  208. extern int
  209. __big_delete (bufp, ndx)
  210. BUFHEAD    *bufp;
  211. int    ndx;
  212. {
  213.     register    BUFHEAD        *rbufp = bufp;
  214.     register    BUFHEAD        *last_bfp = NULL;
  215.     char    *cp;
  216.     u_short    *bp = (u_short *)bufp->page;
  217.     u_short    *xbp;
  218.     u_short    pageno = 0;
  219.     u_short    off, free_sp;
  220.     int    key_done = 0;
  221.     int    n;
  222.  
  223.     while (!key_done || (bp[2] != FULL_KEY_DATA)) {
  224.         if ( bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA ) key_done = 1;
  225.  
  226.         /*
  227.         If there is freespace left on a FULL_KEY_DATA page,
  228.         then the data is short and fits entirely on this
  229.         page, and this is the last page.
  230.         */
  231.         if ( bp[2] == FULL_KEY_DATA && FREESPACE(bp) ) break;
  232.         pageno = bp[bp[0]-1];
  233.         rbufp->flags |= BUF_MOD;
  234.         rbufp = __get_buf ( pageno, rbufp, 0 );
  235.         if ( last_bfp ) __free_ovflpage(last_bfp);
  236.         last_bfp = rbufp;
  237.         if ( !rbufp ) return(-1);            /* Error */
  238.         bp = (u_short *)rbufp->page;
  239.     }
  240.  
  241.     /* 
  242.         If we get here then rbufp points to the last page of
  243.         the big key/data pair.  Bufp points to the first
  244.         one -- it should now be empty pointing to the next
  245.         page after this pair.  Can't free it because we don't
  246.         have the page pointing to it.
  247.     */
  248.  
  249.     /* This is information from the last page of the pair */
  250.     n = bp[0];
  251.     pageno = bp[n-1];
  252.  
  253.     /* Now, bp is the first page of the pair */
  254.     bp = (u_short *)bufp->page;
  255.     if ( n > 2 ) {
  256.         /* There is an overflow page */
  257.         bp[1] = pageno;
  258.         bp[2] = OVFLPAGE;
  259.         bufp->ovfl = rbufp->ovfl;
  260.     } else {
  261.         /* This is the last page */
  262.         bufp->ovfl = NULL;
  263.     }
  264.     n -= 2;
  265.     bp[0] = n;
  266.     FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
  267.     OFFSET(bp) = hashp->BSIZE - 1;
  268.  
  269.     bufp->flags |= BUF_MOD;
  270.     if ( rbufp ) __free_ovflpage(rbufp);
  271.     if ( last_bfp != rbufp ) __free_ovflpage(last_bfp);
  272.  
  273.     hashp->NKEYS--;
  274.     return(0);
  275. }
  276.  
  277. /*
  278.     0 = key not found
  279.     -1 = get next overflow page
  280.     -2 means key not found and this is big key/data
  281.     -3 error
  282. */
  283. extern int
  284. __find_bigpair(bufp, ndx, key, size )
  285. BUFHEAD    *bufp;
  286. int    ndx;
  287. char    *key;
  288. int    size;
  289. {
  290.     register    u_short    *bp = (u_short *)bufp->page;
  291.     register    char    *p = bufp->page;
  292.     int        ksize = size;
  293.     char    *kkey = key;
  294.     u_short    bytes;
  295.  
  296.  
  297.     for ( bytes = hashp->BSIZE - bp[ndx]; 
  298.       bytes <= size && bp[ndx+1] == PARTIAL_KEY; 
  299.       bytes = hashp->BSIZE - bp[ndx] ) {
  300.  
  301.     if ( bcmp ( p+bp[ndx], kkey, bytes ))return(-2);
  302.     kkey += bytes;
  303.     ksize -= bytes;
  304.     bufp = __get_buf ( bp[ndx+2], bufp, 0 );
  305.     if ( !bufp ) {
  306.         return(-3);
  307.     }
  308.     p = bufp->page;
  309.     bp = (u_short *)p;
  310.     ndx = 1;
  311.     }
  312.  
  313.     if ( (bytes != ksize) || bcmp ( p+bp[ndx], kkey, bytes )) {
  314. #ifdef HASH_STATISTICS
  315.     hash_collisions++;
  316. #endif
  317.     return(-2);
  318.     }
  319.     else return (ndx);
  320. }
  321.  
  322.  
  323. /*
  324.     Given the buffer pointer of the first overflow page of a big pair, 
  325.     find the end of the big pair
  326.  
  327.     This will set bpp to the buffer header of the last page of the big pair.  
  328.     It will return the pageno of the overflow page following the last page of 
  329.     the pair; 0 if there isn't any (i.e. big pair is the last key in the 
  330.     bucket)
  331. */
  332. extern u_short
  333. __find_last_page ( bpp )
  334. BUFHEAD    **bpp;
  335. {
  336.     int    n;
  337.     u_short    pageno;
  338.     BUFHEAD    *bufp = *bpp;
  339.     u_short    *bp = (u_short *)bufp->page;
  340.  
  341.     while ( 1 ) {
  342.         n = bp[0];
  343.  
  344.         /*
  345.         This is the last page if:
  346.             the tag is FULL_KEY_DATA and either
  347.                 only 2 entries
  348.                 OVFLPAGE marker is explicit
  349.                 there is freespace on the page
  350.         */
  351.         if ( bp[2] == FULL_KEY_DATA &&
  352.          ((n == 2) ||  (bp[n] == OVFLPAGE) || (FREESPACE(bp)) ) ) break;
  353.  
  354.         pageno = bp[n-1];
  355.         bufp = __get_buf ( pageno, bufp, 0 );
  356.         if ( !bufp ) return (0);        /* Need to indicate an error! */
  357.         bp = (u_short *)bufp->page;
  358.     }
  359.  
  360.     *bpp = bufp;
  361.     if ( bp[0] > 2 ) return ( bp[3] );
  362.     else return(0);
  363. }
  364.  
  365.  
  366. /*
  367.     Return the data for the key/data pair
  368.     that begins on this page at this index
  369.     (index should always be 1)
  370. */
  371. extern int
  372. __big_return ( bufp, ndx, val, set_current )
  373. BUFHEAD    *bufp;
  374. int    ndx;
  375. DBT    *val;
  376. int    set_current;
  377. {
  378.     BUFHEAD    *save_p;
  379.     u_short    save_addr;
  380.     u_short    *bp = (u_short *)bufp->page;
  381.     u_short    off, len;
  382.     char    *cp, *tp;
  383.  
  384.     while ( bp[ndx+1] == PARTIAL_KEY ) {
  385.     bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  386.     if ( !bufp ) return(-1);
  387.     bp = (u_short *)bufp->page;
  388.     ndx = 1;
  389.     }
  390.  
  391.     if ( bp[ndx+1] == FULL_KEY ) {
  392.     bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  393.     if ( !bufp ) return(-1);
  394.     bp = (u_short *)bufp->page;
  395.     save_p = bufp;
  396.     save_addr = save_p->addr;
  397.     off = bp[1];
  398.     len = 0;
  399.     } else if (!FREESPACE(bp)) {
  400.     /*
  401.         This is a hack.  We can't distinguish between
  402.         FULL_KEY_DATA that contains complete data or
  403.         incomplete data, so we require that if the
  404.         data  is complete, there is at least 1 byte
  405.         of free space left.
  406.     */
  407.     off = bp[bp[0]];
  408.     len = bp[1] - off;
  409.     save_p = bufp;
  410.     save_addr = bufp->addr;
  411.     bufp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  412.     if ( !bufp ) return(-1);
  413.     bp = (u_short *)bufp->page;
  414.     } else {
  415.     /* The data is all on one page */
  416.     tp = (char *)bp;
  417.     off = bp[bp[0]];
  418.     val->data = (u_char *)tp + off;
  419.     val->size = bp[1] - off;
  420.     if ( set_current ) {
  421.         if ( bp[0] == 2 ) {        /* No more buckets in chain */
  422.         hashp->cpage = NULL;
  423.         hashp->cbucket++;
  424.         hashp->cndx=1;
  425.         } else  {
  426.         hashp->cpage = __get_buf ( bp[bp[0]-1], bufp, 0 );
  427.         if ( !hashp->cpage )return(-1);
  428.         hashp->cndx = 1;
  429.         if ( !((u_short *)hashp->cpage->page)[0] ) {
  430.             hashp->cbucket++;
  431.             hashp->cpage = NULL;
  432.         }
  433.         }
  434.     }
  435.     return(0);
  436.     }
  437.     
  438.     val->size = collect_data ( bufp, len, set_current );
  439.     if ( val->size == -1 ) {
  440.     return(-1);
  441.     }
  442.     if ( save_p->addr != save_addr ) {
  443.     /* We are pretty short on buffers */
  444.     errno = EINVAL;        /* OUT OF BUFFERS */
  445.     return(-1);
  446.     }
  447.     bcopy ( (save_p->page)+off, hashp->tmp_buf, len );
  448.     val->data = (u_char *)hashp->tmp_buf;
  449.     return(0);
  450. }
  451.  
  452. /*
  453.     Count how big the total datasize is by
  454.     recursing through the pages.  Then allocate
  455.     a buffer and copy the data as you recurse up.
  456. */
  457. static int
  458. collect_data ( bufp, len, set )
  459. BUFHEAD    *bufp;
  460. int    len;
  461. int    set;
  462. {
  463.     register    char    *p = bufp->page;
  464.     register    u_short    *bp = (u_short *)p;
  465.     u_short    save_addr;
  466.     int    mylen, totlen;
  467.     BUFHEAD    *xbp;
  468.  
  469.     mylen = hashp->BSIZE - bp[1];
  470.     save_addr = bufp->addr;
  471.  
  472.     if ( bp[2] == FULL_KEY_DATA ) {    /* End of Data */
  473.     totlen = len + mylen;
  474.     if ( hashp->tmp_buf ) free (hashp->tmp_buf);
  475.     hashp->tmp_buf = (char *)malloc ( totlen );
  476.     if ( !hashp->tmp_buf ) {
  477.         return(-1);
  478.     }
  479.     if ( set ) {
  480.         hashp->cndx = 1;
  481.         if ( bp[0] == 2 ) {        /* No more buckets in chain */
  482.         hashp->cpage = NULL;
  483.         hashp->cbucket++;
  484.         } else  {
  485.         hashp->cpage = __get_buf ( bp[bp[0]-1], bufp, 0 );
  486.         if (!hashp->cpage) {
  487.             return(-1);
  488.         } else if ( !((u_short *)hashp->cpage->page)[0] ) {
  489.             hashp->cbucket++;
  490.             hashp->cpage = NULL;
  491.         }
  492.         }
  493.     }
  494.     } else {
  495.     xbp = __get_buf ( bp[bp[0]-1], bufp, 0 );
  496.     if ( !xbp || ((totlen = collect_data ( xbp, len + mylen, set )) < 1) ) {
  497.         return(-1);
  498.     }
  499.     }
  500.     if ( bufp->addr != save_addr ) {
  501.     errno = EINVAL;        /* Out of buffers */
  502.     return(-1);
  503.     }
  504.     bcopy ( (bufp->page) + bp[1], &hashp->tmp_buf[len], mylen );
  505.     return ( totlen );
  506. }
  507.  
  508. /*
  509.     Fill in the key and data
  510.     for this big pair 
  511. */
  512. extern int
  513. __big_keydata ( bufp, ndx, key, val, set )
  514. BUFHEAD    *bufp;
  515. int    ndx;
  516. DBT    *key, *val;
  517. int    set;
  518. {
  519.     key->size = collect_key ( bufp, 0, val, set );
  520.     if ( key->size == -1 ) {
  521.     return (-1);
  522.     }
  523.     key->data = (u_char *)hashp->tmp_key;
  524.     return(0);
  525. }
  526.  
  527. /*
  528.     Count how big the total key size is by
  529.     recursing through the pages.  Then collect
  530.     the data, allocate a buffer and copy the key as
  531.     you recurse up.
  532. */
  533. static int
  534. collect_key ( bufp, len, val, set )
  535. BUFHEAD    *bufp;
  536. int    len;
  537. DBT    *val;
  538. int    set;
  539. {
  540.     char    *p = bufp->page;
  541.     u_short    *bp = (u_short *)p;
  542.     u_short    save_addr;
  543.     int    mylen, totlen;
  544.     BUFHEAD    *xbp;
  545.  
  546.     mylen = hashp->BSIZE - bp[1];
  547.  
  548.     save_addr = bufp->addr;
  549.     totlen = len + mylen;
  550.     if ( bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA ) {/* End of Key */
  551.     if ( hashp->tmp_key ) free (hashp->tmp_key);
  552.     hashp->tmp_key = (char *)malloc ( totlen );
  553.     if ( !hashp->tmp_key ) {
  554.         return(-1);
  555.     }
  556.     __big_return ( bufp, 1, val, set );
  557.     } else {
  558.     xbp = __get_buf (bp[bp[0]-1], bufp, 0);
  559.     if ( !xbp || ((totlen = collect_key (xbp, totlen, val, set)) < 1 ) ) {
  560.         return(-1);
  561.     }
  562.     }
  563.     if ( bufp->addr != save_addr ) {
  564.     errno = EINVAL;        /* MIS -- OUT OF BUFFERS */
  565.     return (-1);
  566.     }
  567.     bcopy ( (bufp->page) + bp[1], &hashp->tmp_key[len], mylen );
  568.     return ( totlen );
  569. }
  570.  
  571.  
  572. /*
  573.     return 0 => OK
  574.        -1 => error
  575. */
  576. extern int
  577. __big_split ( op, np, big_keyp, addr, obucket, ret )
  578. BUFHEAD    *op;        /* Pointer to where to put keys that go in old bucket */
  579. BUFHEAD    *np;        /* Pointer to new bucket page */
  580. BUFHEAD    *big_keyp;    /* Pointer to first page containing the big key/data */
  581. u_short    addr;        /* Address of big_keyp */
  582. u_int    obucket;    /* Old Bucket */
  583. SPLIT_RETURN    *ret;
  584. {
  585.     register    u_short    *prev_pagep;
  586.     register    BUFHEAD    *tmpp;
  587.     register    u_short     *tp;
  588.     BUFHEAD    *bp = big_keyp;
  589.     u_short    off, free_space;
  590.     u_short    n;
  591.  
  592.     DBT        key, val;
  593.  
  594.     u_int    change;
  595.  
  596.     /* Now figure out where the big key/data goes */
  597.     if (__big_keydata ( big_keyp, 1, &key, &val, 0 )) {
  598.     return(-1);
  599.     }
  600.     change = (__call_hash ( key.data, key.size ) != obucket );
  601.  
  602.     if ( ret->next_addr = __find_last_page ( &big_keyp ) ) {
  603.     if (!(ret->nextp = __get_buf ( ret->next_addr, big_keyp, 0 ))) {
  604.         return(-1);;
  605.     }
  606.     } else {
  607.     ret->nextp = NULL;
  608.     }
  609.  
  610.     /* Now make one of np/op point to the big key/data pair */
  611.     assert(np->ovfl == NULL);
  612.     if ( change ) tmpp = np;
  613.     else tmpp = op;
  614.  
  615.     tmpp->flags |= BUF_MOD;
  616. #ifdef DEBUG1
  617.     fprintf ( stderr, "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
  618.         (tmpp->ovfl?tmpp->ovfl->addr:0), 
  619.         (bp?bp->addr:0) );
  620. #endif
  621.     tmpp->ovfl = bp;        /* one of op/np point to big_keyp */
  622.     tp = (u_short *)tmpp->page;
  623.     assert ( FREESPACE(tp) >= OVFLSIZE);
  624.     n = tp[0];
  625.     off = OFFSET(tp);
  626.     free_space = FREESPACE(tp);
  627.     tp[++n] = addr;
  628.     tp[++n] = OVFLPAGE;
  629.     tp[0] = n;
  630.     OFFSET(tp) = off;
  631.     FREESPACE(tp) = free_space - OVFLSIZE;
  632.  
  633.     /* 
  634.     Finally, set the new and old return values.
  635.     BIG_KEYP contains a pointer to the last page of the big key_data pair.
  636.     Make sure that big_keyp has no following page (2 elements) or create
  637.     an empty following page.
  638.     */
  639.  
  640.     ret->newp = np;
  641.     ret->oldp = op;
  642.  
  643.     tp = (u_short *)big_keyp->page;
  644.     big_keyp->flags |= BUF_MOD;
  645.     if ( tp[0] > 2 ) {
  646.     /* 
  647.         There may be either one or two offsets on this page 
  648.         If there is one, then the overflow page is linked on
  649.         normally and tp[4] is OVFLPAGE.  If there are two, tp[4]
  650.         contains the second offset and needs to get stuffed in
  651.         after the next overflow page is added
  652.     */
  653.     n = tp[4];        
  654.     free_space = FREESPACE(tp);
  655.     off = OFFSET(tp);
  656.     tp[0] -= 2;
  657.     FREESPACE(tp) = free_space + OVFLSIZE;
  658.     OFFSET(tp) = off;
  659.     tmpp = __add_ovflpage ( big_keyp );
  660.     if ( !tmpp ) {
  661.         return(-1);
  662.     }
  663.     tp[4] = n;
  664.     } else {
  665.     tmpp = big_keyp;
  666.     }
  667.  
  668.     if ( change ) ret->newp = tmpp;
  669.     else ret->oldp = tmpp;
  670.  
  671.     return(0);
  672. }
  673.